//
// Created by ASUS on 2023/10/15.
//

/*
给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：

对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。
返回 grid 的乘积矩阵。



示例 1：

输入：grid = [[1,2],[3,4]]
输出：[[24,12],[8,6]]
解释：p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
所以答案是 [[24,12],[8,6]] 。
示例 2：

输入：grid = [[12345],[2],[1]]
输出：[[2],[0],[0]]
解释：p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0 ，所以 p[0][1] = 0
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0 ，所以 p[0][2] = 0
所以答案是 [[2],[0],[0]] 。


提示：

1 <= n == grid.length <= 105
1 <= m == grid[i].length <= 105
2 <= n * m <= 105
1 <= grid[i][j] <= 109
 */
#include <bits/stdc++.h>
using namespace std;
const int MOD=12345;
vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
	int m=grid.size(),n=grid[0].size();
	vector<vector<int>> ans(m,vector<int>(n,1));
	long long suf=1;
	for(int i=m-1;i>=0;i--){
		for(int j=n-1;j>=0;j--){
			ans[i][j]=ans[i][j]*suf%MOD;
			suf=suf*grid[i][j]%MOD;
		}
	}
	long long pre=1;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			ans[i][j]=ans[i][j]*pre%MOD;
			pre=pre*grid[i][j]%MOD;
		}
	}
	return ans;
}